package com.promote.algorithm;

/**
 * @ClassName IsValidSudoku
 * Description 有效的数独
 * @Author LiZiHao
 * Date 2022/3/9 14:47
 * @Version 1.0
 **/
public class IsValidSudoku {

    /**
     * 就是每行，每列以及对应3*3的单元格内只能有1-9这9个数字，并且不能有重复的。
     *
     * 我们首先遍历9宫格的所有元素，然后使用3个二维数组遍历，记录对应的行，列以及3*3单元格是否有某个数字，如果出现冲突，直接返回false。
     *
     * @param board
     * @return
     */
    public boolean isValidSudoKu(char[][] board) {
        int length = board.length;

        //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
        //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
        int[][] line = new int[length][length];
        int[][] column = new int[length][length];
        int[][] cell = new int[length][length];

        for (int i = 0; i < length; ++i) {
            for (int j = 0; j < length; ++j) {
                //如果没有填数字，直接跳过
                if (board[i][j] == '.') {
                    continue;
                }
                //num 是当前格子的数字
                int num = board[i][j] - '0' - 1;
                //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
                int k = i / 3 * 3 + j / 3;
                //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
                //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
                if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0) {
                    return false;
                }
                //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
                line[i][num] = column[j][num] = cell[k][num] = 1;

            }
        }

        return true;
    }
}
